package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //骑士拨号器
    public static int MOD = 1000000007;
    public static int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
    public int knightDialer(int n) {
        int[][][] dp= new int[4][3][n + 1];
        int ans = 0;
        for(int step = 1; step <= n; step++){
            for(int i = 0; i < 4; i++){
                for(int j = 0; j < 3; j++){
                    if(i == 3 && (j == 0 || j == 2)){
                        dp[i][j][step] = 0;
                    }else if(step == 1){
                        dp[i][j][step] = 1;
                    }else{
                        for(int[] dir : dirs){
                            int ni = i + dir[0];
                            int nj = j + dir[1];
                            if(0 <= ni && ni < 4 && 0 <= nj && nj < 3){
                                dp[i][j][step] = (dp[i][j][step] + dp[ni][nj][step - 1]) % MOD;
                            }
                        }
                    }
                    if(step == n){
                        ans = (ans + dp[i][j][step]) % MOD;
                    }
                }
            }
        }
        return ans;
    }
}
